import java.util.*;

public class Leetcode {
}

//leetcode:1926:迷宫中离入口最近的出口
class Solution1 {
    //确定走向
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    public int nearestExit(char[][] maze, int[] entrance) {
        int m = maze.length, n = maze[0].length;
        //设置布尔数组判断是否走过
        boolean[][] visits = new boolean[m][n];
        visits[entrance[0]][entrance[1]] = true;

        //创建队列存入可以走的位置
        Queue<int[]> q = new LinkedList<>();
        q.offer(entrance);

        //一层一层的找可以走的位置
        int ret = 0;
        while (!q.isEmpty()) {
            ret++;
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                int[] s = q.poll();
                int a = s[0], b = s[1];
                for (int k = 0; k < 4; k++) {
                    int x = a + dx[k], y = b + dy[k];
                    if (x >= 0 && x < m && y >= 0 && y < n && !visits[x][y] && maze[x][y] == '.') {
                        //如果此时可以走的位置为边界就代表已经找到出口
                        if (x == 0 || x == m-1 || y == 0 || y == n-1) {
                            return ret;
                        }
                        visits[x][y] = true;
                        q.offer(new int[]{x,y});
                    }
                }
            }
        }
        return -1;
    }
}

//leetcode:433:最小基因变化
class Solution2 {
    public int minMutation(String startGene, String endGene, String[] bank) {
        //创建两个哈希表
        Set<String> visits = new HashSet<>();
        Set<String> hash = new HashSet<>();

        //hash存入有效的基因
        for(String s : bank) hash.add(s);

        //如果最后要变化的基因在库中不存在，返回-1
        if(!hash.contains(endGene)) return -1;
        //如果原本的基因就是最后要变化的基因，返回0
        if(startGene.equals(endGene)) return 0;

        //创建一个数组存入每一次的可能变化
        char[] change = {'A','C','G','T'};

        //创建队列存入有效的基因变化
        Queue<String> q = new LinkedList<>();
        q.add(startGene);
        visits.add(startGene);

        //一层一层的进行查找有效的基因
        int ret = 0;
        while (!q.isEmpty()) {
            ret++;
            int sz = q.size();
            while (sz-- != 0) {
                String str = q.poll();
                //一个基因有8处可以发生变化
                for(int i = 0; i < 8 ; i++) {
                    char[] ch = str.toCharArray();
                    //变化的字符为4个：即change数组
                    for (int j = 0; j < 4; j++) {
                        ch[i] = change[j];
                        String next = new String(ch);
                        if (hash.contains(next) && !visits.contains(next)) {
                            //如果我们变化后的基因为最终基因，直接返回
                            if(endGene.equals(next)) return ret;
                            //如果不是最终基因，就将有效的基因放入队列中，进行变化
                            q.add(next);
                            visits.add(next);
                        }
                    }
                }
            }
        }
        return -1;
    }
}

//leetcode:127:单词接龙
class Solution3 {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        //创建两个哈希表
        Set<String> hash = new HashSet<>();
        Set<String> visits = new HashSet<>();

        //hash存入有效的单词变化
        for (String s : wordList) {
            hash.add(s);
        }
        //判断最后变化的单词是否在有效的单词中，不在返回0
        if (!hash.contains(endWord))
            return 0;
        //如果我们最初的单词就是我们要最终得到的单词就返回1
        if (beginWord.equals(endWord))
            return 1;

        //创建队列存入有效的单词
        Queue<String> q = new LinkedList<>();
        q.add(beginWord);
        int ret = 1;
        while (!q.isEmpty()) {
            ret++;
            int sz = q.size();
            while (sz-- != 0) {
                String str = q.poll();
                //根据得到的单词长度去得到有几个位置可以进行变化
                for (int i = 0; i < str.length(); i++) {
                    char[] ch = str.toCharArray();
                    //变化的范围为'a'~'z'
                    for (char j = 'a'; j <= 'z'; j++) {
                        ch[i] = j;//更新
                        String tmp = new String(ch);
                        if (hash.contains(tmp) && !visits.contains(tmp)) {
                            //如果此时变化的单词为最终要得到的单词，直接返回
                            if (tmp.equals(endWord))
                                return ret;
                            q.add(tmp);
                            visits.add(tmp);
                        }
                    }
                }
            }
        }
        return 0;
    }
}